{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Sort Integers by The Power Value"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #memoization #dynamic-programming #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #记忆化搜索 #动态规划 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: getKth"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #将整数按权重排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>我们将整数 <code>x</code>&nbsp;的 <strong>权重</strong> 定义为按照下述规则将 <code>x</code>&nbsp;变成 <code>1</code>&nbsp;所需要的步数：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>如果&nbsp;<code>x</code>&nbsp;是偶数，那么&nbsp;<code>x = x / 2</code></li>\n",
    "\t<li>如果&nbsp;<code>x</code>&nbsp;是奇数，那么&nbsp;<code>x = 3 * x + 1</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>比方说，x=3 的权重为 7 。因为 3 需要 7 步变成 1 （3 --&gt; 10 --&gt; 5 --&gt; 16 --&gt; 8 --&gt; 4 --&gt; 2 --&gt; 1）。</p>\n",
    "\n",
    "<p>给你三个整数&nbsp;<code>lo</code>，&nbsp;<code>hi</code> 和&nbsp;<code>k</code>&nbsp;。你的任务是将区间&nbsp;<code>[lo, hi]</code>&nbsp;之间的整数按照它们的权重&nbsp;<strong>升序排序&nbsp;</strong>，如果大于等于 2 个整数有&nbsp;<strong>相同</strong>&nbsp;的权重，那么按照数字自身的数值&nbsp;<strong>升序排序</strong>&nbsp;。</p>\n",
    "\n",
    "<p>请你返回区间&nbsp;<code>[lo, hi]</code>&nbsp;之间的整数按权重排序后的第&nbsp;<code>k</code>&nbsp;个数。</p>\n",
    "\n",
    "<p>注意，题目保证对于任意整数&nbsp;<code>x</code>&nbsp;<code>（lo &lt;= x &lt;= hi）</code>&nbsp;，它变成&nbsp;<code>1</code> 所需要的步数是一个 32 位有符号整数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>lo = 12, hi = 15, k = 2\n",
    "<strong>输出：</strong>13\n",
    "<strong>解释：</strong>12 的权重为 9（12 --&gt; 6 --&gt; 3 --&gt; 10 --&gt; 5 --&gt; 16 --&gt; 8 --&gt; 4 --&gt; 2 --&gt; 1）\n",
    "13 的权重为 9\n",
    "14 的权重为 17\n",
    "15 的权重为 17\n",
    "区间内的数按权重排序以后的结果为 [12,13,14,15] 。对于 k = 2 ，答案是第二个整数也就是 13 。\n",
    "注意，12 和 13 有相同的权重，所以我们按照它们本身升序排序。14 和 15 同理。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>lo = 7, hi = 11, k = 4\n",
    "<strong>输出：</strong>7\n",
    "<strong>解释：</strong>区间内整数 [7, 8, 9, 10, 11] 对应的权重为 [16, 3, 19, 6, 14] 。\n",
    "按权重排序后得到的结果为 [8, 10, 11, 7, 9] 。\n",
    "排序后数组中第 4 个数字为 7 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= lo &lt;= hi &lt;= 1000</code></li>\n",
    "\t<li><code>1 &lt;= k &lt;= hi - lo + 1</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [sort-integers-by-the-power-value](https://leetcode.cn/problems/sort-integers-by-the-power-value/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [sort-integers-by-the-power-value](https://leetcode.cn/problems/sort-integers-by-the-power-value/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['12\\n15\\n2', '7\\n11\\n4']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKth(self, lo: int, hi: int, k: int) -> int:\n",
    "        def steps(n):\n",
    "            result = 0\n",
    "            while n!=1:\n",
    "                if n%2 == 1: n = 3*n+1\n",
    "                else: n = n/2\n",
    "                result += 1\n",
    "            return result\n",
    "        result = [i for i in range(lo,hi+1)]\n",
    "        result.sort(key = steps)\n",
    "        return result[k-1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKth(self, lo: int, hi: int, k: int) -> int:\n",
    "        '''def steps(n):\n",
    "            result = 0\n",
    "            while n!=1:\n",
    "                if n%2 == 1: n = 3*n+1\n",
    "                else: n = n/2\n",
    "                result += 1\n",
    "            return result\n",
    "        result = [i for i in range(lo,hi+1)]\n",
    "        result.sort(key = steps)\n",
    "        return result[k-1]'''\n",
    "\n",
    "        def dfs(k):\n",
    "            if k == 1: return 0\n",
    "            return 1+dfs(k//2) if k%2 == 0 else 1+dfs(3*k+1)\n",
    "        result = [i for i in range(lo,hi+1)]\n",
    "        result.sort(key = dfs)\n",
    "        return result[k-1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKth(self, lo: int, hi: int, k: int) -> int:\n",
    "        res = []\n",
    "        for x in range(lo, hi+1):\n",
    "            res.append([x, self.getWeight(x)])\n",
    "        ans = sorted(res, key=lambda x: (x[1], x[0]))\n",
    "        return ans[k-1][0]\n",
    "    \n",
    "    def getWeight(self, num):\n",
    "        ans = 0\n",
    "        while num != 1:\n",
    "            if num % 2 == 0:\n",
    "                num //= 2\n",
    "            else:\n",
    "                num = num * 3 + 1\n",
    "            ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "@cache\n",
    "def f(x):\n",
    "    if x == 1: return 0\n",
    "    if x & 1: return f(3*x+1)+1\n",
    "    return f(x//2)+1\n",
    "\n",
    "class Solution:\n",
    "    def getKth(self, lo: int, hi: int, k: int) -> int:\n",
    "        return sorted(range(lo,hi+1),key=lambda x:(f(x),x))[k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKth(self, lo: int, hi: int, k: int) -> int:\n",
    "        a=[0, 0, 1, 7, 2, 5, 8, 16, 3, 19, 6, 14, 9, 9, 17, 17, 4, 12, 20, 20, 7, 7, 15, 15, 10, 23, 10, 111, 18, 18, 18, 106, 5, 26, 13, 13, 21, 21, 21, 34, 8, 109, 8, 29, 16, 16, 16, 104, 11, 24, 24, 24, 11, 11, 112, 112, 19, 32, 19, 32, 19, 19, 107, 107, 6, 27, 27, 27, 14, 14, 14, 102, 22, 115, 22, 14, 22, 22, 35, 35, 9, 22, 110, 110, 9, 9, 30, 30, 17, 30, 17, 92, 17, 17, 105, 105, 12, 118, 25, 25, 25, 25, 25, 87, 12, 38, 12, 100, 113, 113, 113, 69, 20, 12, 33, 33, 20, 20, 33, 33, 20, 95, 20, 46, 108, 108, 108, 46, 7, 121, 28, 28, 28, 28, 28, 41, 15, 90, 15, 41, 15, 15, 103, 103, 23, 116, 116, 116, 23, 23, 15, 15, 23, 36, 23, 85, 36, 36, 36, 54, 10, 98, 23, 23, 111, 111, 111, 67, 10, 49, 10, 124, 31, 31, 31, 80, 18, 31, 31, 31, 18, 18, 93, 93, 18, 44, 18, 44, 106, 106, 106, 44, 13, 119, 119, 119, 26, 26, 26, 119, 26, 18, 26, 39, 26, 26, 88, 88, 13, 39, 39, 39, 13, 13, 101, 101, 114, 26, 114, 52, 114, 114, 70, 70, 21, 52, 13, 13, 34, 34, 34, 127, 21, 83, 21, 127, 34, 34, 34, 52, 21, 21, 96, 96, 21, 21, 47, 47, 109, 47, 109, 65, 109, 109, 47, 47, 8, 122, 122, 122, 29, 29, 29, 78, 29, 122, 29, 21, 29, 29, 42, 42, 16, 29, 91, 91, 16, 16, 42, 42, 16, 42, 16, 60, 104, 104, 104, 42, 24, 29, 117, 117, 117, 117, 117, 55, 24, 73, 24, 117, 16, 16, 16, 42, 24, 37, 37, 37, 24, 24, 86, 86, 37, 130, 37, 37, 37, 37, 55, 55, 11, 24, 99, 99, 24, 24, 24, 143, 112, 50, 112, 24, 112, 112, 68, 68, 11, 112, 50, 50, 11, 11, 125, 125, 32, 125, 32, 125, 32, 32, 81, 81, 19, 125, 32, 32, 32, 32, 32, 50, 19, 45, 19, 45, 94, 94, 94, 45, 19, 19, 45, 45, 19, 19, 45, 45, 107, 63, 107, 58, 107, 107, 45, 45, 14, 32, 120, 120, 120, 120, 120, 120, 27, 58, 27, 76, 27, 27, 120, 120, 27, 19, 19, 19, 27, 27, 40, 40, 27, 40, 27, 133, 89, 89, 89, 133, 14, 133, 40, 40, 40, 40, 40, 32, 14, 58, 14, 53, 102, 102, 102, 40, 115, 27, 27, 27, 115, 115, 53, 53, 115, 27, 115, 53, 71, 71, 71, 97, 22, 115, 53, 53, 14, 14, 14, 40, 35, 128, 35, 128, 35, 35, 128, 128, 22, 35, 84, 84, 22, 22, 128, 128, 35, 35, 35, 27, 35, 35, 53, 53, 22, 48, 22, 22, 97, 97, 97, 141, 22, 48, 22, 141, 48, 48, 48, 97, 110, 22, 48, 48, 110, 110, 66, 66, 110, 61, 110, 35, 48, 48, 48, 61, 9, 35, 123, 123, 123, 123, 123, 61, 30, 123, 30, 123, 30, 30, 79, 79, 30, 30, 123, 123, 30, 30, 22, 22, 30, 22, 30, 48, 43, 43, 43, 136, 17, 43, 30, 30, 92, 92, 92, 43, 17, 136, 17, 30, 43, 43, 43, 87, 17, 43, 43, 43, 17, 17, 61, 61, 105, 56, 105, 30, 105, 105, 43, 43, 25, 30, 30, 30, 118, 118, 118, 30, 118, 56, 118, 118, 118, 118, 56, 56, 25, 74, 74, 74, 25, 25, 118, 118, 17, 56, 17, 69, 17, 17, 43, 43, 25, 131, 38, 38, 38, 38, 38, 69, 25, 131, 25, 131, 87, 87, 87, 131, 38, 25, 131, 131, 38, 38, 38, 38, 38, 30, 38, 30, 56, 56, 56, 131, 12, 51, 25, 25, 100, 100, 100, 38, 25, 144, 25, 100, 25, 25, 144, 144, 113, 51, 51, 51, 113, 113, 25, 25, 113, 51, 113, 144, 69, 69, 69, 95, 12, 64, 113, 113, 51, 51, 51, 64, 12, 64, 12, 38, 126, 126, 126, 38, 33, 126, 126, 126, 33, 33, 126, 126, 33, 126, 33, 64, 82, 82, 82, 170, 20, 33, 126, 126, 33, 33, 33, 64, 33, 25, 33, 25, 33, 33, 51, 51, 20, 46, 46, 46, 20, 20, 46, 46, 95, 33, 95, 139, 95, 95, 46, 46, 20, 139, 20, 20, 46, 46, 46, 95, 20, 90, 20, 46, 46, 46, 46, 139, 108, 20, 64, 64, 108, 108, 59, 59, 108, 33, 108, 152, 46, 46, 46, 59, 15, 33, 33, 33, 121, 121, 121, 152, 121, 33, 121, 59, 121, 121, 121, 121, 28, 121, 59, 59, 28, 28, 77, 77, 28, 77, 28, 103, 121, 121, 121, 72, 28, 59, 20, 20, 20, 20, 20, 72, 28, 46, 28, 134, 41, 41, 41, 134, 28, 41, 41, 41, 28, 28, 134, 134, 90, 134, 90, 41, 90, 90, 134, 134, 15, 28, 134, 134, 41, 41, 41, 85, 41, 41, 41, 41, 41, 41, 33, 33, 15, 59, 59, 59, 15, 15, 54, 54, 103, 28, 103, 147, 103, 103, 41, 41, 116, 147, 28, 28, 28, 28, 28, 178, 116, 147, 116, 28, 54, 54, 54, 147, 116, 116, 28, 28, 116, 116, 54, 54, 72, 147, 72, 46, 72, 72, 98, 98, 23, 67, 116, 116, 54, 54, 54, 116, 15, 67, 15, 54, 15, 15, 41, 41, 36, 129, 129, 129, 36, 36, 129, 129, 36, 129, 36, 67, 129, 129, 129, 116, 23, 129, 36, 36, 85, 85, 85, 129, 23, 173, 23, 85, 129, 129, 129, 36, 36, 36, 36, 36, 36, 36, 28, 28, 36, 28, 36, 28, 54, 54, 54, 129, 23, 49, 49, 49, 23, 23, 23, 142, 98, 49, 98, 36, 98, 98, 142, 142, 23, 98, 49, 49, 23, 23, 142, 142, 49, 23, 49, 36, 49, 49, 98, 98, 111, 93, 23, 23, 49, 49, 49, 49, 111]\n",
    "        nums = [ i for i in range(lo,hi+1)]\n",
    "        nums.sort(key=lambda x:a[x])\n",
    "        return nums[k-1]\n",
    "        \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\r\n",
    "class Solution:\r\n",
    "    def getKth(self, lo: int, hi: int, k: int) -> int:\r\n",
    "        @lru_cache\r\n",
    "        def get(x):\r\n",
    "            if x==1:\r\n",
    "                return 0\r\n",
    "            if x%2:\r\n",
    "                t = get(x*3+1)\r\n",
    "            else:\r\n",
    "                t = get(x//2)\r\n",
    "            return 1+t\r\n",
    "        arr = [i for i in range(lo,hi+1)]\r\n",
    "        arr.sort(key=lambda x:(get(x),x))\r\n",
    "        return arr[k-1]\r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKth(self, lo: int, hi: int, k: int) -> int:\n",
    "        map_ = dict()\n",
    "\n",
    "        def search(num):\n",
    "            if num == 1:\n",
    "                return 0\n",
    "            if num % 2 == 0:\n",
    "                new_num = num // 2\n",
    "            else:\n",
    "                new_num = 3 * num + 1\n",
    "            if new_num in map_:\n",
    "                rs = map_[new_num] + 1\n",
    "                return rs\n",
    "            rs = search(new_num) + 1\n",
    "            map_[new_num] = rs\n",
    "            return rs\n",
    "        tmp = dict()\n",
    "        for num in range(lo, hi + 1):\n",
    "            map_ = dict()\n",
    "            tmp[num] = search(num)\n",
    "        tmp = sorted(tmp.items(), key=lambda x: x[1])\n",
    "        return tmp[k - 1][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKth(self, lo: int, hi: int, k: int) -> int:\n",
    "\n",
    "        ws = [0 for i in range(2  * hi)]\n",
    "\n",
    "        def get_weight(num):\n",
    "            if len(ws) > num  and  ws[num]:\n",
    "                return ws[num]\n",
    "            if num == 1:\n",
    "                w =  1\n",
    "            elif num % 2 == 1:\n",
    "                w = get_weight(num * 3+1 ) + 1\n",
    "            else:\n",
    "                w = get_weight(int(num/2) ) + 1\n",
    "            if len(ws) > num:\n",
    "                ws[num] = w \n",
    "            return w\n",
    "        \n",
    "        wss = [(get_weight(i),i) for i in range(lo,hi+1)]\n",
    "        wss.sort()\n",
    "        return wss[k-1][1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKth(self, lo: int, hi: int, k: int) -> int:\n",
    "        a={\"1\": 0, \"2\": 1, \"3\": 7, \"4\": 2, \"5\": 5, \"6\": 8, \"7\": 16, \"8\": 3, \"9\": 19, \"10\": 6, \"11\": 14, \"12\": 9, \"13\": 9, \"14\": 17, \"15\": 17, \"16\": 4, \"17\": 12, \"18\": 20, \"19\": 20, \"20\": 7, \"21\": 7, \"22\": 15, \"23\": 15, \"24\": 10, \"25\": 23, \"26\": 10, \"27\": 111, \"28\": 18, \"29\": 18, \"30\": 18, \"31\": 106, \"32\": 5, \"33\": 26, \"34\": 13, \"35\": 13, \"36\": 21, \"37\": 21, \"38\": 21, \"39\": 34, \"40\": 8, \"41\": 109, \"42\": 8, \"43\": 29, \"44\": 16, \"45\": 16, \"46\": 16, \"47\": 104, \"48\": 11, \"49\": 24, \"50\": 24, \"51\": 24, \"52\": 11, \"53\": 11, \"54\": 112, \"55\": 112, \"56\": 19, \"57\": 32, \"58\": 19, \"59\": 32, \"60\": 19, \"61\": 19, \"62\": 107, \"63\": 107, \"64\": 6, \"65\": 27, \"66\": 27, \"67\": 27, \"68\": 14, \"69\": 14, \"70\": 14, \"71\": 102, \"72\": 22, \"73\": 115, \"74\": 22, \"75\": 14, \"76\": 22, \"77\": 22, \"78\": 35, \"79\": 35, \"80\": 9, \"81\": 22, \"82\": 110, \"83\": 110, \"84\": 9, \"85\": 9, \"86\": 30, \"87\": 30, \"88\": 17, \"89\": 30, \"90\": 17, \"91\": 92, \"92\": 17, \"93\": 17, \"94\": 105, \"95\": 105, \"96\": 12, \"97\": 118, \"98\": 25, \"99\": 25, \"100\": 25, \"101\": 25, \"102\": 25, \"103\": 87, \"104\": 12, \"105\": 38, \"106\": 12, \"107\": 100, \"108\": 113, \"109\": 113, \"110\": 113, \"111\": 69, \"112\": 20, \"113\": 12, \"114\": 33, \"115\": 33, \"116\": 20, \"117\": 20, \"118\": 33, \"119\": 33, \"120\": 20, \"121\": 95, \"122\": 20, \"123\": 46, \"124\": 108, \"125\": 108, \"126\": 108, \"127\": 46, \"128\": 7, \"129\": 121, \"130\": 28, \"131\": 28, \"132\": 28, \"133\": 28, \"134\": 28, \"135\": 41, \"136\": 15, \"137\": 90, \"138\": 15, \"139\": 41, \"140\": 15, \"141\": 15, \"142\": 103, \"143\": 103, \"144\": 23, \"145\": 116, \"146\": 116, \"147\": 116, \"148\": 23, \"149\": 23, \"150\": 15, \"151\": 15, \"152\": 23, \"153\": 36, \"154\": 23, \"155\": 85, \"156\": 36, \"157\": 36, \"158\": 36, \"159\": 54, \"160\": 10, \"161\": 98, \"162\": 23, \"163\": 23, \"164\": 111, \"165\": 111, \"166\": 111, \"167\": 67, \"168\": 10, \"169\": 49, \"170\": 10, \"171\": 124, \"172\": 31, \"173\": 31, \"174\": 31, \"175\": 80, \"176\": 18, \"177\": 31, \"178\": 31, \"179\": 31, \"180\": 18, \"181\": 18, \"182\": 93, \"183\": 93, \"184\": 18, \"185\": 44, \"186\": 18, \"187\": 44, \"188\": 106, \"189\": 106, \"190\": 106, \"191\": 44, \"192\": 13, \"193\": 119, \"194\": 119, \"195\": 119, \"196\": 26, \"197\": 26, \"198\": 26, \"199\": 119, \"200\": 26, \"201\": 18, \"202\": 26, \"203\": 39, \"204\": 26, \"205\": 26, \"206\": 88, \"207\": 88, \"208\": 13, \"209\": 39, \"210\": 39, \"211\": 39, \"212\": 13, \"213\": 13, \"214\": 101, \"215\": 101, \"216\": 114, \"217\": 26, \"218\": 114, \"219\": 52, \"220\": 114, \"221\": 114, \"222\": 70, \"223\": 70, \"224\": 21, \"225\": 52, \"226\": 13, \"227\": 13, \"228\": 34, \"229\": 34, \"230\": 34, \"231\": 127, \"232\": 21, \"233\": 83, \"234\": 21, \"235\": 127, \"236\": 34, \"237\": 34, \"238\": 34, \"239\": 52, \"240\": 21, \"241\": 21, \"242\": 96, \"243\": 96, \"244\": 21, \"245\": 21, \"246\": 47, \"247\": 47, \"248\": 109, \"249\": 47, \"250\": 109, \"251\": 65, \"252\": 109, \"253\": 109, \"254\": 47, \"255\": 47, \"256\": 8, \"257\": 122, \"258\": 122, \"259\": 122, \"260\": 29, \"261\": 29, \"262\": 29, \"263\": 78, \"264\": 29, \"265\": 122, \"266\": 29, \"267\": 21, \"268\": 29, \"269\": 29, \"270\": 42, \"271\": 42, \"272\": 16, \"273\": 29, \"274\": 91, \"275\": 91, \"276\": 16, \"277\": 16, \"278\": 42, \"279\": 42, \"280\": 16, \"281\": 42, \"282\": 16, \"283\": 60, \"284\": 104, \"285\": 104, \"286\": 104, \"287\": 42, \"288\": 24, \"289\": 29, \"290\": 117, \"291\": 117, \"292\": 117, \"293\": 117, \"294\": 117, \"295\": 55, \"296\": 24, \"297\": 73, \"298\": 24, \"299\": 117, \"300\": 16, \"301\": 16, \"302\": 16, \"303\": 42, \"304\": 24, \"305\": 37, \"306\": 37, \"307\": 37, \"308\": 24, \"309\": 24, \"310\": 86, \"311\": 86, \"312\": 37, \"313\": 130, \"314\": 37, \"315\": 37, \"316\": 37, \"317\": 37, \"318\": 55, \"319\": 55, \"320\": 11, \"321\": 24, \"322\": 99, \"323\": 99, \"324\": 24, \"325\": 24, \"326\": 24, \"327\": 143, \"328\": 112, \"329\": 50, \"330\": 112, \"331\": 24, \"332\": 112, \"333\": 112, \"334\": 68, \"335\": 68, \"336\": 11, \"337\": 112, \"338\": 50, \"339\": 50, \"340\": 11, \"341\": 11, \"342\": 125, \"343\": 125, \"344\": 32, \"345\": 125, \"346\": 32, \"347\": 125, \"348\": 32, \"349\": 32, \"350\": 81, \"351\": 81, \"352\": 19, \"353\": 125, \"354\": 32, \"355\": 32, \"356\": 32, \"357\": 32, \"358\": 32, \"359\": 50, \"360\": 19, \"361\": 45, \"362\": 19, \"363\": 45, \"364\": 94, \"365\": 94, \"366\": 94, \"367\": 45, \"368\": 19, \"369\": 19, \"370\": 45, \"371\": 45, \"372\": 19, \"373\": 19, \"374\": 45, \"375\": 45, \"376\": 107, \"377\": 63, \"378\": 107, \"379\": 58, \"380\": 107, \"381\": 107, \"382\": 45, \"383\": 45, \"384\": 14, \"385\": 32, \"386\": 120, \"387\": 120, \"388\": 120, \"389\": 120, \"390\": 120, \"391\": 120, \"392\": 27, \"393\": 58, \"394\": 27, \"395\": 76, \"396\": 27, \"397\": 27, \"398\": 120, \"399\": 120, \"400\": 27, \"401\": 19, \"402\": 19, \"403\": 19, \"404\": 27, \"405\": 27, \"406\": 40, \"407\": 40, \"408\": 27, \"409\": 40, \"410\": 27, \"411\": 133, \"412\": 89, \"413\": 89, \"414\": 89, \"415\": 133, \"416\": 14, \"417\": 133, \"418\": 40, \"419\": 40, \"420\": 40, \"421\": 40, \"422\": 40, \"423\": 32, \"424\": 14, \"425\": 58, \"426\": 14, \"427\": 53, \"428\": 102, \"429\": 102, \"430\": 102, \"431\": 40, \"432\": 115, \"433\": 27, \"434\": 27, \"435\": 27, \"436\": 115, \"437\": 115, \"438\": 53, \"439\": 53, \"440\": 115, \"441\": 27, \"442\": 115, \"443\": 53, \"444\": 71, \"445\": 71, \"446\": 71, \"447\": 97, \"448\": 22, \"449\": 115, \"450\": 53, \"451\": 53, \"452\": 14, \"453\": 14, \"454\": 14, \"455\": 40, \"456\": 35, \"457\": 128, \"458\": 35, \"459\": 128, \"460\": 35, \"461\": 35, \"462\": 128, \"463\": 128, \"464\": 22, \"465\": 35, \"466\": 84, \"467\": 84, \"468\": 22, \"469\": 22, \"470\": 128, \"471\": 128, \"472\": 35, \"473\": 35, \"474\": 35, \"475\": 27, \"476\": 35, \"477\": 35, \"478\": 53, \"479\": 53, \"480\": 22, \"481\": 48, \"482\": 22, \"483\": 22, \"484\": 97, \"485\": 97, \"486\": 97, \"487\": 141, \"488\": 22, \"489\": 48, \"490\": 22, \"491\": 141, \"492\": 48, \"493\": 48, \"494\": 48, \"495\": 97, \"496\": 110, \"497\": 22, \"498\": 48, \"499\": 48, \"500\": 110, \"501\": 110, \"502\": 66, \"503\": 66, \"504\": 110, \"505\": 61, \"506\": 110, \"507\": 35, \"508\": 48, \"509\": 48, \"510\": 48, \"511\": 61, \"512\": 9, \"513\": 35, \"514\": 123, \"515\": 123, \"516\": 123, \"517\": 123, \"518\": 123, \"519\": 61, \"520\": 30, \"521\": 123, \"522\": 30, \"523\": 123, \"524\": 30, \"525\": 30, \"526\": 79, \"527\": 79, \"528\": 30, \"529\": 30, \"530\": 123, \"531\": 123, \"532\": 30, \"533\": 30, \"534\": 22, \"535\": 22, \"536\": 30, \"537\": 22, \"538\": 30, \"539\": 48, \"540\": 43, \"541\": 43, \"542\": 43, \"543\": 136, \"544\": 17, \"545\": 43, \"546\": 30, \"547\": 30, \"548\": 92, \"549\": 92, \"550\": 92, \"551\": 43, \"552\": 17, \"553\": 136, \"554\": 17, \"555\": 30, \"556\": 43, \"557\": 43, \"558\": 43, \"559\": 87, \"560\": 17, \"561\": 43, \"562\": 43, \"563\": 43, \"564\": 17, \"565\": 17, \"566\": 61, \"567\": 61, \"568\": 105, \"569\": 56, \"570\": 105, \"571\": 30, \"572\": 105, \"573\": 105, \"574\": 43, \"575\": 43, \"576\": 25, \"577\": 30, \"578\": 30, \"579\": 30, \"580\": 118, \"581\": 118, \"582\": 118, \"583\": 30, \"584\": 118, \"585\": 56, \"586\": 118, \"587\": 118, \"588\": 118, \"589\": 118, \"590\": 56, \"591\": 56, \"592\": 25, \"593\": 74, \"594\": 74, \"595\": 74, \"596\": 25, \"597\": 25, \"598\": 118, \"599\": 118, \"600\": 17, \"601\": 56, \"602\": 17, \"603\": 69, \"604\": 17, \"605\": 17, \"606\": 43, \"607\": 43, \"608\": 25, \"609\": 131, \"610\": 38, \"611\": 38, \"612\": 38, \"613\": 38, \"614\": 38, \"615\": 69, \"616\": 25, \"617\": 131, \"618\": 25, \"619\": 131, \"620\": 87, \"621\": 87, \"622\": 87, \"623\": 131, \"624\": 38, \"625\": 25, \"626\": 131, \"627\": 131, \"628\": 38, \"629\": 38, \"630\": 38, \"631\": 38, \"632\": 38, \"633\": 30, \"634\": 38, \"635\": 30, \"636\": 56, \"637\": 56, \"638\": 56, \"639\": 131, \"640\": 12, \"641\": 51, \"642\": 25, \"643\": 25, \"644\": 100, \"645\": 100, \"646\": 100, \"647\": 38, \"648\": 25, \"649\": 144, \"650\": 25, \"651\": 100, \"652\": 25, \"653\": 25, \"654\": 144, \"655\": 144, \"656\": 113, \"657\": 51, \"658\": 51, \"659\": 51, \"660\": 113, \"661\": 113, \"662\": 25, \"663\": 25, \"664\": 113, \"665\": 51, \"666\": 113, \"667\": 144, \"668\": 69, \"669\": 69, \"670\": 69, \"671\": 95, \"672\": 12, \"673\": 64, \"674\": 113, \"675\": 113, \"676\": 51, \"677\": 51, \"678\": 51, \"679\": 64, \"680\": 12, \"681\": 64, \"682\": 12, \"683\": 38, \"684\": 126, \"685\": 126, \"686\": 126, \"687\": 38, \"688\": 33, \"689\": 126, \"690\": 126, \"691\": 126, \"692\": 33, \"693\": 33, \"694\": 126, \"695\": 126, \"696\": 33, \"697\": 126, \"698\": 33, \"699\": 64, \"700\": 82, \"701\": 82, \"702\": 82, \"703\": 170, \"704\": 20, \"705\": 33, \"706\": 126, \"707\": 126, \"708\": 33, \"709\": 33, \"710\": 33, \"711\": 64, \"712\": 33, \"713\": 25, \"714\": 33, \"715\": 25, \"716\": 33, \"717\": 33, \"718\": 51, \"719\": 51, \"720\": 20, \"721\": 46, \"722\": 46, \"723\": 46, \"724\": 20, \"725\": 20, \"726\": 46, \"727\": 46, \"728\": 95, \"729\": 33, \"730\": 95, \"731\": 139, \"732\": 95, \"733\": 95, \"734\": 46, \"735\": 46, \"736\": 20, \"737\": 139, \"738\": 20, \"739\": 20, \"740\": 46, \"741\": 46, \"742\": 46, \"743\": 95, \"744\": 20, \"745\": 90, \"746\": 20, \"747\": 46, \"748\": 46, \"749\": 46, \"750\": 46, \"751\": 139, \"752\": 108, \"753\": 20, \"754\": 64, \"755\": 64, \"756\": 108, \"757\": 108, \"758\": 59, \"759\": 59, \"760\": 108, \"761\": 33, \"762\": 108, \"763\": 152, \"764\": 46, \"765\": 46, \"766\": 46, \"767\": 59, \"768\": 15, \"769\": 33, \"770\": 33, \"771\": 33, \"772\": 121, \"773\": 121, \"774\": 121, \"775\": 152, \"776\": 121, \"777\": 33, \"778\": 121, \"779\": 59, \"780\": 121, \"781\": 121, \"782\": 121, \"783\": 121, \"784\": 28, \"785\": 121, \"786\": 59, \"787\": 59, \"788\": 28, \"789\": 28, \"790\": 77, \"791\": 77, \"792\": 28, \"793\": 77, \"794\": 28, \"795\": 103, \"796\": 121, \"797\": 121, \"798\": 121, \"799\": 72, \"800\": 28, \"801\": 59, \"802\": 20, \"803\": 20, \"804\": 20, \"805\": 20, \"806\": 20, \"807\": 72, \"808\": 28, \"809\": 46, \"810\": 28, \"811\": 134, \"812\": 41, \"813\": 41, \"814\": 41, \"815\": 134, \"816\": 28, \"817\": 41, \"818\": 41, \"819\": 41, \"820\": 28, \"821\": 28, \"822\": 134, \"823\": 134, \"824\": 90, \"825\": 134, \"826\": 90, \"827\": 41, \"828\": 90, \"829\": 90, \"830\": 134, \"831\": 134, \"832\": 15, \"833\": 28, \"834\": 134, \"835\": 134, \"836\": 41, \"837\": 41, \"838\": 41, \"839\": 85, \"840\": 41, \"841\": 41, \"842\": 41, \"843\": 41, \"844\": 41, \"845\": 41, \"846\": 33, \"847\": 33, \"848\": 15, \"849\": 59, \"850\": 59, \"851\": 59, \"852\": 15, \"853\": 15, \"854\": 54, \"855\": 54, \"856\": 103, \"857\": 28, \"858\": 103, \"859\": 147, \"860\": 103, \"861\": 103, \"862\": 41, \"863\": 41, \"864\": 116, \"865\": 147, \"866\": 28, \"867\": 28, \"868\": 28, \"869\": 28, \"870\": 28, \"871\": 178, \"872\": 116, \"873\": 147, \"874\": 116, \"875\": 28, \"876\": 54, \"877\": 54, \"878\": 54, \"879\": 147, \"880\": 116, \"881\": 116, \"882\": 28, \"883\": 28, \"884\": 116, \"885\": 116, \"886\": 54, \"887\": 54, \"888\": 72, \"889\": 147, \"890\": 72, \"891\": 46, \"892\": 72, \"893\": 72, \"894\": 98, \"895\": 98, \"896\": 23, \"897\": 67, \"898\": 116, \"899\": 116, \"900\": 54, \"901\": 54, \"902\": 54, \"903\": 116, \"904\": 15, \"905\": 67, \"906\": 15, \"907\": 54, \"908\": 15, \"909\": 15, \"910\": 41, \"911\": 41, \"912\": 36, \"913\": 129, \"914\": 129, \"915\": 129, \"916\": 36, \"917\": 36, \"918\": 129, \"919\": 129, \"920\": 36, \"921\": 129, \"922\": 36, \"923\": 67, \"924\": 129, \"925\": 129, \"926\": 129, \"927\": 116, \"928\": 23, \"929\": 129, \"930\": 36, \"931\": 36, \"932\": 85, \"933\": 85, \"934\": 85, \"935\": 129, \"936\": 23, \"937\": 173, \"938\": 23, \"939\": 85, \"940\": 129, \"941\": 129, \"942\": 129, \"943\": 36, \"944\": 36, \"945\": 36, \"946\": 36, \"947\": 36, \"948\": 36, \"949\": 36, \"950\": 28, \"951\": 28, \"952\": 36, \"953\": 28, \"954\": 36, \"955\": 28, \"956\": 54, \"957\": 54, \"958\": 54, \"959\": 129, \"960\": 23, \"961\": 49, \"962\": 49, \"963\": 49, \"964\": 23, \"965\": 23, \"966\": 23, \"967\": 142, \"968\": 98, \"969\": 49, \"970\": 98, \"971\": 36, \"972\": 98, \"973\": 98, \"974\": 142, \"975\": 142, \"976\": 23, \"977\": 98, \"978\": 49, \"979\": 49, \"980\": 23, \"981\": 23, \"982\": 142, \"983\": 142, \"984\": 49, \"985\": 23, \"986\": 49, \"987\": 36, \"988\": 49, \"989\": 49, \"990\": 98, \"991\": 98, \"992\": 111, \"993\": 93, \"994\": 23, \"995\": 23, \"996\": 49, \"997\": 49, \"998\": 49, \"999\": 49, \"1000\": 111}\n",
    "        b=[(a[str(i)],i) for i in range(lo,hi+1)]\n",
    "        ans=sorted(b,key=lambda x:x[0]+0.00001*x[1])\n",
    "        # print(ans)\n",
    "        return ans[k-1][1]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKth(self, lo: int, hi: int, k: int) -> int:\n",
    "\n",
    "        @lru_cache\n",
    "        def dfs(x):\n",
    "            if x == 1:\n",
    "                return 0\n",
    "            if x % 2 == 0:\n",
    "                return dfs(x//2) + 1\n",
    "            else:\n",
    "                return dfs(3*x+1) + 1\n",
    "\n",
    "        f = [0] * (hi-lo+1)\n",
    "        for i in range(len(f)):\n",
    "            f[i] = [dfs(lo+i), lo+i]\n",
    "        f.sort()\n",
    "        return f[k-1][1]\n",
    "         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def getKth(self, lo: int, hi: int, k: int) -> int:\n",
    "        @lru_cache\n",
    "        def getF(x):\n",
    "            if x == 1:\n",
    "                return 0\n",
    "            t,yu=divmod(x,2)\n",
    "            return 1+ (getF(x * 3 + 1) if yu else getF(t)) \n",
    "        \n",
    "        v = list(range(lo, hi + 1))\n",
    "        v.sort(key=lambda x: (getF(x), x))\n",
    "        return v[k - 1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def getKth(self, lo: int, hi: int, k: int) -> int:\n",
    "        @lru_cache\n",
    "        def getF(x):\n",
    "            if x == 1:\n",
    "                return 0\n",
    "            t,yu=divmod(x,2)\n",
    "            return 1+ (getF(x * 3 + 1) if yu else getF(t)) \n",
    "        \n",
    "        v = list(range(lo, hi + 1))\n",
    "        v.sort(key=lambda x: (getF(x), x))\n",
    "        return v[k - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWeight(self,n):\n",
    "        cnt=0\n",
    "        while n!=1:\n",
    "            if n&1:\n",
    "                n=3*n+1\n",
    "            else:\n",
    "                n>>=1\n",
    "            cnt+=1\n",
    "        return cnt\n",
    "\n",
    "    def getKth(self, lo: int, hi: int, k: int) -> int:\n",
    "        \n",
    "        self.num2weight = {}\n",
    "        self.nums = [i for i in range(lo,hi+1)]\n",
    "        for i in range(lo,hi+1):\n",
    "            self.num2weight[i]=self.getWeight(i)\n",
    "        \n",
    "        def merge(left,right):\n",
    "            i,j = 0,0\n",
    "            temp = []\n",
    "            while i<len(left) and j<len(right):\n",
    "                if self.num2weight[left[i]] < self.num2weight[right[j]]:\n",
    "                    temp.append(left[i])\n",
    "                    i+=1\n",
    "                elif self.num2weight[left[i]] == self.num2weight[right[j]]:\n",
    "                    if left[i]<right[j]:\n",
    "                        temp.append(left[i])\n",
    "                        i+=1\n",
    "                    else:\n",
    "                        temp.append(right[j])\n",
    "                        j+=1\n",
    "                else:\n",
    "                    temp.append(right[j])\n",
    "                    j+=1\n",
    "            while i<len(left):\n",
    "                temp.append(left[i])\n",
    "                i+=1\n",
    "            while j<len(right):\n",
    "                temp.append(right[j])\n",
    "                j+=1\n",
    "            return temp\n",
    "\n",
    "        def mergeSort(nums):\n",
    "            if len(nums)<=1:\n",
    "                return nums\n",
    "            middle = len(nums)//2\n",
    "            left = mergeSort(nums[:middle])\n",
    "            right = mergeSort(nums[middle:])\n",
    "            return merge(left,right)\n",
    "\n",
    "        return mergeSort(self.nums)[k-1]\n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKth(self, lo: int, hi: int, k: int) -> int:\n",
    "\n",
    "        ws = [0 for i in range(3  * hi + 1)]\n",
    "\n",
    "        def get_weight(num):\n",
    "            if len(ws) > num  and  ws[num]:\n",
    "                return ws[num]\n",
    "            if num == 1:\n",
    "                w =  1\n",
    "            elif num % 2 == 1:\n",
    "                w = get_weight(num * 3+1 ) + 1\n",
    "            else:\n",
    "                w = get_weight(int(num/2) ) + 1\n",
    "            if len(ws) > num:\n",
    "                ws[num] = w \n",
    "            return w\n",
    "        \n",
    "        wss = [(get_weight(i),i) for i in range(lo,hi+1)]\n",
    "        wss.sort()\n",
    "        return wss[k-1][1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKth(self, lo: int, hi: int, k: int) -> int:\n",
    "        @lru_cache(maxsize=300)\n",
    "        def getWeight(x):\n",
    "            if x==1:\n",
    "                return 0\n",
    "            if x&1:\n",
    "                return getWeight(x*3+1)+1\n",
    "            else:\n",
    "                return getWeight(x//2)+1\n",
    "        v = list(range(lo, hi + 1))\n",
    "        v.sort(key=lambda x: (getWeight(x), x))\n",
    "        return v[k - 1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKth(self, lo: int, hi: int, k: int) -> int:\n",
    "        def helper(num):\n",
    "            if num == 1:\n",
    "                return 0\n",
    "            if num in memo:\n",
    "                return memo[num]\n",
    "            ans = 1\n",
    "            if num & 1:\n",
    "                ans += helper(3*num+1)\n",
    "            else:\n",
    "                ans += helper(num >> 1)\n",
    "            return ans\n",
    "\n",
    "        memo = dict()\n",
    "        hq = []\n",
    "        import heapq\n",
    "        for num in range(lo, hi+1):\n",
    "            if num not in memo:\n",
    "                step = helper(num)\n",
    "                memo[num] = step\n",
    "            else:\n",
    "                step = memo[num]\n",
    "            # print(memo)\n",
    "            if len(hq) <= hi-lo+1-k:\n",
    "                heapq.heappush(hq, (step, num))\n",
    "            else:\n",
    "                heapq.heappushpop(hq, (step, num))\n",
    "        return hq[0][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKth(self, lo: int, hi: int, k: int) -> int:\n",
    "        f = {1:0}\n",
    "        from functools import lru_cache\n",
    "        @lru_cache(None)\n",
    "        def getWeight(num):\n",
    "            if not f.get(num) is None:\n",
    "                return f[num]\n",
    "            else:\n",
    "                if num%2:\n",
    "                    f[num] = getWeight(num*3+1)+1\n",
    "                else:\n",
    "                    f[num] = getWeight(num/2)+1\n",
    "            return f[num]\n",
    "            # count = 0\n",
    "            # while(num != 1):\n",
    "            #     if num % 2:\n",
    "            #         num = num*3+1\n",
    "            #     else:\n",
    "            #         num = num/2\n",
    "            #     count += 1\n",
    "            # return count\n",
    "\n",
    "        return sorted(range(lo, hi+1), key=getWeight)[k-1]\n",
    "        \n",
    "    \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def getKth(self, lo: int, hi: int, k: int) -> int:\r\n",
    "\r\n",
    "        # cache = [0] * 1000010\r\n",
    "        @cache\r\n",
    "        def dfs(x):\r\n",
    "            x=int(x)\r\n",
    "            if x==1:\r\n",
    "                return 0\r\n",
    "            # if cache[x]!=0:\r\n",
    "            #     return cache[x]\r\n",
    "            if x % 2 ==0:\r\n",
    "                res = dfs(x/2)+1\r\n",
    "            else:\r\n",
    "                res = dfs(x*3+1)+1\r\n",
    "            # cache[x] = res\r\n",
    "            return res\r\n",
    "            \r\n",
    "        key_value = {}\r\n",
    "        for i in range(lo,hi+1):\r\n",
    "            key_value[i] = dfs(i)\r\n",
    "        # 按值进行排序，如果值相等，按键进行排序\r\n",
    "        sorted_key = dict(sorted(key_value.items(), key=lambda item: (item[1], item[0])))\r\n",
    "\r\n",
    "        keys = list(sorted_key.keys())\r\n",
    "        \r\n",
    "        return keys[k-1]\r\n",
    "\r\n",
    "        \r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKth(self, lo: int, hi: int, k: int) -> int:\n",
    "        \n",
    "        @cache\n",
    "        def dfs(a: int)->int:\n",
    "            if a == 1:\n",
    "                return 0\n",
    "            if a%2 == 0:\n",
    "                return dfs(a/2) +1\n",
    "            else:\n",
    "                return dfs(3*a +1) +1\n",
    "    \n",
    "        v = list(range(lo, hi + 1))\n",
    "        v.sort(key=lambda x: dfs(x))\n",
    "        return v[k - 1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKth(self, lo: int, hi: int, k: int) -> int:\n",
    "        from functools import lru_cache\n",
    "        @lru_cache(None)\n",
    "        def getWeight(num):\n",
    "            if num == 1:\n",
    "                return 0\n",
    "            if num % 2 == 0:\n",
    "                return 1 + getWeight(num / 2)\n",
    "            return 1 + getWeight(num * 3 + 1)\n",
    "        \n",
    "        weights = [(getWeight(i), i) for i in range(lo, hi + 1)]\n",
    "        weights.sort()\n",
    "        return weights[k - 1][1]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKth(self, lo: int, hi: int, k: int) -> int:\n",
    "        # 返回num的权重\n",
    "        def getWeight(num):\n",
    "            # 先搜索字典\n",
    "            if num in m:\n",
    "                return m[num]\n",
    "            elif num == 1:\n",
    "                return 0\n",
    "            elif num % 2 == 0:\n",
    "                return 1 + getWeight(num/2)\n",
    "            else:\n",
    "                return 1 + getWeight(3*num+1)\n",
    "\n",
    "        m = defaultdict(int)  # 创建一个默认值为0的字典，用于存储数字和对应的权重\n",
    "        for i in range(lo, hi+1):  # 遍历从lo到hi的数字\n",
    "            w = getWeight(i)  # 计算当前数字的权重\n",
    "            m[i] = w\n",
    "\n",
    "        arr = sorted(m.keys(), key=lambda x: (m[x], x))  # 根据权重和数字进行排序\n",
    "        return arr[k-1]  # 返回第k个数字\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKth(self, lo: int, hi: int, k: int) -> int:\n",
    "        \n",
    "        @cache\n",
    "        def dfs(a: int)->int:\n",
    "            if a == 1:\n",
    "                return 0\n",
    "            if a%2 == 0:\n",
    "                return dfs(a/2) +1\n",
    "            else:\n",
    "                return dfs(3*a +1) +1\n",
    "    \n",
    "        v = list(range(lo, hi + 1))\n",
    "        v.sort(key=lambda x: (dfs(x), x))\n",
    "        return v[k - 1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKth(self, lo: int, hi: int, k: int) -> int:\n",
    "        \n",
    "        @cache\n",
    "        def count(n):\n",
    "            if n & n - 1 == 0: return (n - 1).bit_count()\n",
    "            if n & 1: return 2 + count(int(1.5 * n + 0.5))\n",
    "            return 1 + count(n // 2)\n",
    "        \n",
    "        return sorted(range(lo, hi + 1), key = lambda n: (count(n), n))[k - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKth(self, lo: int, hi: int, k: int) -> int:\n",
    "        @cache\n",
    "        def getPower(x):\n",
    "            if x == 1:\n",
    "                return 0\n",
    "            return getPower(3 * x + 1) + 1 if x % 2 else getPower(x / 2) + 1\n",
    "\n",
    "        res = list(range(lo, hi+1))\n",
    "        res.sort(key = getPower)\n",
    "\n",
    "        return res[k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKth(self, lo: int, hi: int, k: int) -> int:\n",
    "        @cache\n",
    "        def getPower(x):\n",
    "            if x == 1:\n",
    "                return 0\n",
    "            if x % 2 == 0:\n",
    "                return getPower(x/2) + 1\n",
    "            return getPower(3 * x + 1) + 1\n",
    "\n",
    "        res = list(range(lo, hi+1))\n",
    "        res.sort(key = getPower)\n",
    "\n",
    "        return res[k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKth(self, lo: int, hi: int, k: int) -> int:\n",
    "        memo = {1: 0}\n",
    "        def get_w(num):\n",
    "            if num in memo:\n",
    "                return memo[num]\n",
    "            if num % 2 == 0:\n",
    "                res = get_w(num // 2) + 1\n",
    "            else:\n",
    "                res = get_w(num * 3 + 1) + 1\n",
    "            memo[num] = res\n",
    "            return res\n",
    "        nums = list(range(lo, hi + 1))\n",
    "        k -= 1\n",
    "        def kth(l, r):\n",
    "            if l > r:\n",
    "                return\n",
    "            m, flag = l, (get_w(nums[l]), nums[l])\n",
    "            for i in range(l + 1, r + 1):\n",
    "                if (get_w(nums[i]), nums[i]) < flag:\n",
    "                    m += 1\n",
    "                    nums[i], nums[m] = nums[m], nums[i]\n",
    "            nums[m], nums[l] = nums[l], nums[m]\n",
    "            if m == k:\n",
    "                return nums[m]\n",
    "            elif m < k:\n",
    "                return kth(m + 1, r)\n",
    "            else:\n",
    "                return kth(l, m - 1)\n",
    "        return kth(0, len(nums) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKth(self, lo: int, hi: int, k: int) -> int:\n",
    "        @cache\n",
    "        def f(n):\n",
    "            return 0 if n == 1 else (f(3 * n + 1) if n & 1 else f(n >> 1)) + 1\n",
    "        \n",
    "        ptr = [[] for _ in range(180)]\n",
    "\n",
    "        for i in range(lo, hi + 1):\n",
    "            ptr[f(i)].append(i)\n",
    "        \n",
    "        for l in ptr:\n",
    "            if l:\n",
    "                if k <= len(l):\n",
    "                    return l[k - 1]\n",
    "                k -= len(l)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKth(self, lo: int, hi: int, k: int) -> int:\n",
    "        res=[]\n",
    "        \n",
    "        @cache\n",
    "        def dfs(s):\n",
    "            tmp=0\n",
    "            if s == 1:\n",
    "                return 0\n",
    "            if s%2==0:\n",
    "                tmp+=1+dfs(s/2)\n",
    "            else:\n",
    "                tmp+=1+dfs(3*s+1)\n",
    "            return tmp\n",
    "        for i in range(lo,hi+1):\n",
    "            res.append([dfs(i),i])\n",
    "        res.sort()\n",
    "\n",
    "        return res[k-1][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKth(self, lo: int, hi: int, k: int) -> int:\n",
    "        @cache\n",
    "        def get_pow(x:int) -> int:\n",
    "            if x == 1:\n",
    "                return 0\n",
    "            elif x & 1:\n",
    "                return 1 + get_pow(3 * x +1)\n",
    "            else:\n",
    "                return 1 + get_pow(x // 2)\n",
    "        \n",
    "        pow_list = []\n",
    "        for xx in range(lo,hi+1):\n",
    "            pow_list.append(get_pow(xx))\n",
    "        \n",
    "        ll = [i for i in range(lo,hi+1)]\n",
    "        ll.sort(key=cmp_to_key(lambda a,b:pow_list[a-lo] - pow_list[b-lo] if pow_list[a-lo] - pow_list[b-lo] !=0 else a-b))\n",
    "        return ll[k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKth(self, lo: int, hi: int, k: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(x):\n",
    "            if x == 1:\n",
    "                return 1\n",
    "            return 1+dfs(3*x+1) if x%2 else 1+dfs(x//2)\n",
    "        \n",
    "        return sorted(range(lo, hi+1), key=dfs)[k-1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKth(self, lo: int, hi: int, k: int) -> int:\n",
    "        @cache\n",
    "        def getF(x):\n",
    "            if x == 1:\n",
    "                return 0\n",
    "            return (getF(x * 3 + 1) if x % 2 == 1 else getF(x // 2)) + 1\n",
    "        \n",
    "        v = list(range(lo, hi + 1))\n",
    "        v.sort(key=lambda x: (getF(x), x))\n",
    "        return v[k - 1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKth(self, lo: int, hi: int, k: int) -> int:\n",
    "\n",
    "        seen={}\n",
    "        seen[\"1\"]=0\n",
    "        res={}\n",
    "        \n",
    "        def next_lvl(root,num,cur_lvl,seen):\n",
    "            if str(num) in seen.keys():\n",
    "                res[str(root)]=cur_lvl+seen[str(num)]\n",
    "                return cur_lvl+seen[str(num)]\n",
    "            \n",
    "            next_num=0\n",
    "            if num%2 == 0:\n",
    "                next_num = int(num/2)\n",
    "            else:\n",
    "                next_num = int(3*num+1)\n",
    "            \n",
    "            final_lvl = next_lvl(root,next_num,cur_lvl+1,seen)\n",
    "            seen[str(num)] = final_lvl-cur_lvl\n",
    "            return final_lvl\n",
    "\n",
    "        for num in range(lo,hi+1):\n",
    "            next_lvl(num,num,0,seen)\n",
    "\n",
    "\n",
    "        res_list = [(key,val) for key,val in  res.items()]\n",
    "        res_list.sort(key=lambda x:x[1])\n",
    "        return int(res_list[k-1][0])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKth(self, lo: int, hi: int, k: int) -> int:\n",
    "        @cache\n",
    "        def weight(i):\n",
    "            if i == 1:\n",
    "                return 0\n",
    "            elif i % 2 == 0:\n",
    "                return 1 + weight(i // 2)\n",
    "            return 1 + weight(i * 3 + 1)\n",
    "        nums = sorted(list(range(lo, hi+1)), key=lambda x: weight(x))\n",
    "        return nums[k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKth(self, lo: int, hi: int, k: int) -> int:\n",
    "      @cache\n",
    "      def getWeight(n):\n",
    "        if n == 1:\n",
    "          return 1\n",
    "        return 1 + getWeight(3 * n + 1) if n & 1 else 1 + getWeight(n // 2)\n",
    "\n",
    "      arr = [(getWeight(i), i) for i in range(lo, hi+1)]\n",
    "      arr.sort()\n",
    "      return arr[k-1][1]\n",
    "      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKth(self, lo: int, hi: int, k: int) -> int:\n",
    "        @cache\n",
    "        def step(i:int) -> int:\n",
    "            if i == 1:\n",
    "                return 0\n",
    "            if i % 2 == 0:\n",
    "                return step(i // 2) + 1\n",
    "            else:\n",
    "                return step(3 * i + 1) + 1\n",
    "        base = []\n",
    "        for i in range(lo,hi + 1):\n",
    "            tmp = step(i)\n",
    "            base.append([i,tmp])\n",
    "        base.sort(key = lambda x:(x[1],x[0]))\n",
    "        # print(base)\n",
    "        return base[k - 1][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKth(self, lo: int, hi: int, k: int) -> int:\n",
    "        @cache\n",
    "        def key_f(n):\n",
    "            if n != 1:\n",
    "                if n & 1:\n",
    "                    n = 3 * n + 1\n",
    "                else:\n",
    "                    n >>= 1\n",
    "                return key_f(n) + 1\n",
    "            return 0\n",
    "\n",
    "        return sorted(range(lo, hi + 1), key=key_f)[k - 1]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKth(self, lo: int, hi: int, k: int) -> int:\n",
    "        '''def steps(n):\n",
    "            result = 0\n",
    "            while n!=1:\n",
    "                if n%2 == 1: n = 3*n+1\n",
    "                else: n = n/2\n",
    "                result += 1\n",
    "            return result\n",
    "        result = [i for i in range(lo,hi+1)]\n",
    "        result.sort(key = steps)\n",
    "        return result[k-1]'''\n",
    "        @cache\n",
    "        def dfs(k):\n",
    "            if k == 1: return 0\n",
    "            return 1+dfs(k//2) if k%2 == 0 else 1+dfs(3*k+1)\n",
    "        result = [i for i in range(lo,hi+1)]\n",
    "        result.sort(key = dfs)\n",
    "        return result[k-1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKth(self, lo: int, hi: int, k: int) -> int:\n",
    "        @cache\n",
    "        def getPower(n: int) -> int:\n",
    "            if n == 1:\n",
    "                return 0\n",
    "            return 1 + (getPower(3 * n + 1) if n % 2 else getPower(n // 2))\n",
    "        \n",
    "        q = []\n",
    "        for n in range(lo, hi + 1):\n",
    "            p = getPower(n)\n",
    "            q.append((p, n))\n",
    "        q.sort()\n",
    "        return q[k - 1][1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getKth(self, lo: int, hi: int, k: int) -> int:\n",
    "        \n",
    "        @lru_cache(maxsize=None)\n",
    "        def get_f(n):\n",
    "            if n == 1:\n",
    "                return 0\n",
    "            return (get_f(3 * n + 1) if n % 2 == 1 else get_f(n // 2)) + 1\n",
    "\n",
    "        v = list(range(lo, hi + 1))\n",
    "        v.sort(key=lambda x: (get_f(x), x))\n",
    "        return v[k-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKth(self, lo: int, hi: int, k: int) -> int:\n",
    "        @cache\n",
    "        def count(x):\n",
    "            if x == 1:\n",
    "                return 0\n",
    "            if x % 2 == 0:\n",
    "                return count(x // 2) + 1\n",
    "            return count(x * 3 + 1) + 1\n",
    "\n",
    "        return sorted(range(lo, hi + 1), key=lambda x: (count(x), x))[k - 1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "# from functools import lru_cache\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getKth(self, lo: int, hi: int, k: int) -> int:\n",
    "        res = []\n",
    "        dp = [0] * 1000000\n",
    "        #\n",
    "        # @lru_cache\n",
    "        # def get_pro(num):\n",
    "        #     if num == 1:\n",
    "        #         return 0\n",
    "        #     if dp[num] != 0:\n",
    "        #         return dp[num]\n",
    "        #     if num % 2 == 0:\n",
    "        #         return get_pro(num // 2) + 1\n",
    "        #\n",
    "        #     else:\n",
    "        #         return get_pro(num * 3 + 1) + 1\n",
    "\n",
    "        for i in range(lo, hi + 1):\n",
    "            num = i\n",
    "            while num != 1:\n",
    "                if dp[num]:\n",
    "                    dp[i] += dp[num]\n",
    "                    break\n",
    "                if num % 2 == 0:\n",
    "                    num = num // 2\n",
    "\n",
    "                else:\n",
    "                    num = num * 3 + 1\n",
    "                dp[i] += 1\n",
    "            #\n",
    "            # dp[i] = get_pro(i)\n",
    "            if i >= lo:\n",
    "                bisect.insort(res, (dp[i], i))\n",
    "\n",
    "        return res[k - 1][1]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKth(self, lo: int, hi: int, k: int) -> int:\n",
    "        \n",
    "    \n",
    "        memo = {}\n",
    "        h = 1\n",
    "        i = 0\n",
    "        while h <= hi:\n",
    "            memo[h] = i\n",
    "            i+=1\n",
    "            h<<=1\n",
    "\n",
    "        def w(n, d):\n",
    "            if n in memo:\n",
    "                return memo[n] + d\n",
    "            if n == 1:\n",
    "                return d\n",
    "            if n&1:\n",
    "                memo[n] = w(3*n+1, d+1) - d\n",
    "                return memo[n]+d\n",
    "            else:\n",
    "                memo[n] = w(n>>1, d+1) - d\n",
    "                return memo[n] + d\n",
    "        a = []\n",
    "        for i in range(lo, hi+1):\n",
    "            if i not in memo:\n",
    "                x = w(i,0)\n",
    "            a +=[[memo[i], i]]\n",
    "        a.sort(key=lambda x :[x[0], x[1]])\n",
    "        return a[k-1][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKth(self, lo: int, hi: int, k: int) -> int:\n",
    "        storage={}\n",
    "        def calsteps(val):\n",
    "            if val==1:\n",
    "                return 0\n",
    "            try:\n",
    "                step=storage[val]\n",
    "                return step\n",
    "            except KeyError:\n",
    "                if val%2==0:\n",
    "                    val//=2\n",
    "                else:\n",
    "                    val=3*val+1\n",
    "                step=calsteps(val)\n",
    "                storage[val]=step\n",
    "                return 1+step\n",
    "        raw=list(range(lo,hi+1))\n",
    "        #width=len(raw)\n",
    "        steps=[calsteps(i) for i in raw]\n",
    "        #print(steps)\n",
    "        # if k<=width//2:\n",
    "        #     offset=0\n",
    "        #     while offset!=k+1:\n",
    "        #         mini=offset\n",
    "        #         for i in range(offset,width):\n",
    "        #             if steps[i]<steps[mini]:\n",
    "        #                 mini=i\n",
    "        #             elif steps[i]==steps[mini] and raw[i]<raw[mini]:\n",
    "        #                 mini=i\n",
    "        #         temp=steps[offset]\n",
    "        #         steps[offset]=steps[mini]\n",
    "        #         steps[mini]=temp\n",
    "        #         temp=raw[offset]\n",
    "        #         raw[offset]=raw[mini]\n",
    "        #         raw[mini]=temp\n",
    "        #         offset+=1\n",
    "        #     return raw[k-1]\n",
    "        # else:\n",
    "        #     offset=width-1\n",
    "        #     while offset!=k-2:\n",
    "        #         maxi=offset\n",
    "        #         for i in range(0,offset+1):\n",
    "        #             if steps[i]>steps[maxi]:\n",
    "        #                 maxi=i\n",
    "        #             elif steps[i]==steps[maxi] and raw[i]>raw[maxi]:\n",
    "        #                 maxi=i\n",
    "        #         temp=steps[offset]\n",
    "        #         steps[offset]=steps[maxi]\n",
    "        #         steps[maxi]=temp\n",
    "        #         temp=raw[offset]\n",
    "        #         raw[offset]=raw[maxi]\n",
    "        #         raw[maxi]=temp\n",
    "        #         offset-=1\n",
    "        #     return raw[k-1]\n",
    "        return sorted(range(lo,hi+1),key=lambda x:steps[x-lo])[k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def getKth(self, lo: int, hi: int, k: int) -> int:\r\n",
    "        self.dic = {1:0}\r\n",
    "        def get(val):\r\n",
    "            if val in self.dic:\r\n",
    "                return(self.dic[val])\r\n",
    "            else:\r\n",
    "                if val % 2:\r\n",
    "                    self.dic[val * 3 + 1] = get(val * 3 + 1)\r\n",
    "                    return(self.dic[val * 3 + 1] + 1)\r\n",
    "                else:\r\n",
    "                    self.dic[val // 2] = get(val // 2)\r\n",
    "                    return(self.dic[val // 2] + 1)\r\n",
    "\r\n",
    "        ans = []\r\n",
    "        for i in range(lo, hi + 1):\r\n",
    "            ans.append([get(i), i])\r\n",
    "            # if i not in self.dic:\r\n",
    "            #     flag = False\r\n",
    "            #     tmp = i\r\n",
    "            #     cnt = 0\r\n",
    "            #     while(i != 1):\r\n",
    "            #         if i % 2:\r\n",
    "            #             i = 3 * i + 1\r\n",
    "            #         else:\r\n",
    "            #             i //= 2\r\n",
    "            #         cnt += 1\r\n",
    "            #         if i in self.dic:\r\n",
    "            #             ans.append([self.dic[i] + cnt, tmp])\r\n",
    "            #             self.dic[tmp] = self.dic[i] + cnt\r\n",
    "            #             flag = True\r\n",
    "            #             break\r\n",
    "            #     if not flag:\r\n",
    "            #         self.dic[tmp] = cnt\r\n",
    "            #         ans.append([cnt, tmp])\r\n",
    "            # else:\r\n",
    "            #     ans.append([self.dic[i], i])\r\n",
    "        ans.sort()\r\n",
    "        return(ans[k - 1][1])\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def getKth(self, lo: int, hi: int, k: int) -> int:\r\n",
    "        self.dic = {1:0}\r\n",
    "        def get(val):\r\n",
    "            if val in self.dic:\r\n",
    "                return(self.dic[val])\r\n",
    "            else:\r\n",
    "                if val % 2:\r\n",
    "                    self.dic[val * 3 + 1] = get(val * 3 + 1)\r\n",
    "                    return(self.dic[val * 3 + 1] + 1)\r\n",
    "                else:\r\n",
    "                    self.dic[val // 2] = get(val // 2)\r\n",
    "                    return(self.dic[val // 2] + 1)\r\n",
    "\r\n",
    "        ans = []\r\n",
    "        for i in range(lo, hi + 1):\r\n",
    "            ans.append([get(i), i])\r\n",
    "        ans.sort()\r\n",
    "        return(ans[k - 1][1])\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def getKth(self, lo: int, hi: int, k: int) -> int:\r\n",
    "        self.dic = {1:0}\r\n",
    "        def get(val):\r\n",
    "            if val in self.dic:\r\n",
    "                return(self.dic[val])\r\n",
    "            else:\r\n",
    "                if val % 2:\r\n",
    "                    self.dic[val * 3 + 1] = get(val * 3 + 1)\r\n",
    "                    return(self.dic[val * 3 + 1] + 1)\r\n",
    "                else:\r\n",
    "                    self.dic[val // 2] = get(val // 2)\r\n",
    "                    return(self.dic[val // 2] + 1)\r\n",
    "\r\n",
    "        ans = []\r\n",
    "        for i in range(lo, hi + 1):\r\n",
    "            ans.append([get(i), i])\r\n",
    "        ans.sort()\r\n",
    "        return(ans[k - 1][1])\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKth(self, lo: int, hi: int, k: int) -> int:\n",
    "        dp=dict()\n",
    "        dp[1]=0\n",
    "        def dfs(i):\n",
    "            if i==1:\n",
    "                return 0\n",
    "            elif i in dp:\n",
    "                return dp[i]\n",
    "            if i&1:\n",
    "                dp[i]=dfs((3*i+1)//2)+2\n",
    "            else:\n",
    "                dp[i]=dfs(i//2)+1\n",
    "            return dp[i]\n",
    "        for i in range(lo,hi+1):\n",
    "            if i not in dp:\n",
    "                dfs(i)\n",
    "        ans=sorted(list(range(lo,hi+1)),key=lambda x: (dp[x],x))\n",
    "        return ans[k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKth(self, lo: int, hi: int, k: int) -> int:\n",
    "        # 计算各个数的权重,然后排序即可\n",
    "        get_next = lambda x: 3 * x + 1 if x % 2 else x // 2\n",
    "        cache = collections.defaultdict(lambda: -1)  # 记忆化搜索\n",
    "        cache[1] = 0\n",
    "\n",
    "        def count(num):\n",
    "            t = get_next(num)\n",
    "            cache[num] = cache[t] + 1 if cache[t] != -1 else count(t) + 1\n",
    "            return cache[num]\n",
    "\n",
    "        cnt = []\n",
    "        for i in range(lo, hi + 1):  # 构造元组\n",
    "            cnt.append(tuple((count(i), i)))\n",
    "        cnt.sort()  # 排序\n",
    "        return cnt[k - 1][1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def getKth(self, lo: int, hi: int, k: int) -> int:\r\n",
    "        self.dic = {1:0}\r\n",
    "        def get_weight(val):\r\n",
    "            if val in self.dic:\r\n",
    "                return(self.dic[val])\r\n",
    "            else:\r\n",
    "                if val % 2:\r\n",
    "                    self.dic[val] = get_weight(val * 3 + 1) + 1\r\n",
    "                else:\r\n",
    "                    self.dic[val] = get_weight(val // 2) + 1\r\n",
    "                return(self.dic[val])\r\n",
    "\r\n",
    "        ans = []\r\n",
    "        for val in range(lo, hi + 1):\r\n",
    "            ans.append([get_weight(val), val])\r\n",
    "        ans.sort()\r\n",
    "        return(ans[k - 1][1])\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def getKth(self, lo: int, hi: int, k: int) -> int:\r\n",
    "        self.dic = {1:0}\r\n",
    "        def get_weight(val):\r\n",
    "            if val in self.dic:\r\n",
    "                return(self.dic[val])\r\n",
    "            else:\r\n",
    "                if val % 2:\r\n",
    "                    self.dic[val] = get_weight(val * 3 + 1) + 1\r\n",
    "                else:\r\n",
    "                    self.dic[val] = get_weight(val // 2) + 1\r\n",
    "                return(self.dic[val])\r\n",
    "\r\n",
    "        ans = []\r\n",
    "        for val in range(lo, hi + 1):\r\n",
    "            ans.append([get_weight(val), val])\r\n",
    "        ans.sort()\r\n",
    "        return(ans[k - 1][1])\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKth(self, lo: int, hi: int, k: int) -> int:\n",
    "        res=[]\n",
    "        self.dct={}\n",
    "        def get_step(x):\n",
    "            if(x==1):\n",
    "                return 0\n",
    "            if(x in self.dct):\n",
    "                return self.dct[x]\n",
    "            else:\n",
    "                if(x%2==0):\n",
    "                    x/=2\n",
    "                else:\n",
    "                    x=3*x+1\n",
    "                tep=get_step(x)\n",
    "                self.dct[x]=tep\n",
    "                return tep+1\n",
    "        for i in range(lo,hi+1):\n",
    "            x=i\n",
    "            step=0\n",
    "            if(x not in self.dct):\n",
    "                tep=get_step(x)\n",
    "                res.append([i,tep])\n",
    "                self.dct[x]=tep\n",
    "            else:\n",
    "                res.append([i,self.dct[x]])\n",
    "        res=sorted(res, key = lambda x:x[1])\n",
    "        return res[k-1][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKth(self, lo: int, hi: int, k: int) -> int:\n",
    "        f = {1: 0}\n",
    "        @cache\n",
    "        def getF(x):\n",
    "            if x in f:\n",
    "                return f[x]\n",
    "            f[x] = (getF(x * 3 + 1) if x % 2 == 1 else getF(x // 2)) + 1\n",
    "            return f[x]\n",
    "        \n",
    "        v = list(range(lo, hi + 1))\n",
    "        v.sort(key=lambda x: (getF(x), x))\n",
    "        return v[k - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKth(self, lo: int, hi: int, k: int) -> int:\n",
    "        res = []\n",
    "        for x in range(lo, hi+1):\n",
    "            res.append([x, self.getWeight(x)])\n",
    "        ans = sorted(res, key=lambda x: (x[1], x[0]))\n",
    "        return ans[k-1][0]\n",
    "    @cache\n",
    "    def getWeight(self, num):\n",
    "        ans = 0\n",
    "        while num != 1:\n",
    "            if num % 2 == 0:\n",
    "                num //= 2\n",
    "            else:\n",
    "                num = num * 3 + 1\n",
    "            ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKth(self, lo: int, hi: int, k: int) -> int:\n",
    "        def f(n):\n",
    "            if n in self.book:\n",
    "                return self.book[n]\n",
    "            self.book[n] = 0 if n == 1 else (f(3 * n + 1) if n & 1 else f(n >> 1)) + 1\n",
    "            return self.book[n]\n",
    "        self.book = {}\n",
    "        return sorted(range(lo, hi + 1), key=lambda x: f(x))[k - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKth(self, lo: int, hi: int, k: int) -> int:\n",
    "        def f(n):\n",
    "            if n in self.book:\n",
    "                return self.book[n]\n",
    "            self.book[n] = 0 if n == 1 else (f(3 * n + 1) if n & 1 else f(n >> 1)) + 1\n",
    "            return self.book[n]\n",
    "        self.book = {}\n",
    "        return sorted(range(lo, hi + 1), key=lambda x: f(x))[k - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKth(self, lo: int, hi: int, k: int) -> int:\n",
    "        d = {1: 0}\n",
    "        def f(x):\n",
    "            if not x in d:\n",
    "                y = x >> 1\n",
    "                d[x] = f(x + y + 1) + 2 if x & 1 else f(y) + 1\n",
    "            return d[x]\n",
    "        return sorted(range(lo, hi+1), key=f)[k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKth(self, lo: int, hi: int, k: int) -> int:\n",
    "        f = dict()\n",
    "\n",
    "        def search(x):\n",
    "            if x == 1:\n",
    "                return 0\n",
    "            if x in f:\n",
    "                return f[x]\n",
    "            if x % 2== 0:\n",
    "                f[x] = search(x>>1) + 1\n",
    "                return f[x]\n",
    "            else:\n",
    "                f[x] = search((x*3+1)>>1)+ 2\n",
    "                return f[x]\n",
    "        \n",
    "        w = []\n",
    "        for i in range(lo, hi+1):\n",
    "            y = search(i)\n",
    "            w.append((y, i))\n",
    "        w.sort()\n",
    "        return w[k-1][1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKth(self, lo: int, hi: int, k: int) -> int:\n",
    "\n",
    "        f = defaultdict(int)\n",
    "        def dfs(n):\n",
    "            if n == 1:\n",
    "                return 0\n",
    "            if n in f:\n",
    "                return f[n]\n",
    "            if n % 2== 0:\n",
    "                f[n] = dfs(n//2) + 1\n",
    "            else:\n",
    "                f[n] = dfs((3*n+1)//2) + 2\n",
    "            \n",
    "            return f[n] \n",
    "        ans = []\n",
    "        for i in range(lo, hi+1):\n",
    "            d = dfs(i)\n",
    "            ans.append((d, i))\n",
    "        \n",
    "        ans.sort()\n",
    "        return ans[k-1][1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKth(self, lo: int, hi: int, k: int) -> int:\n",
    "        history_dict = dict()\n",
    "\n",
    "        def dfs(cur_val):\n",
    "            if cur_val in history_dict:\n",
    "                return history_dict[cur_val]\n",
    "            elif cur_val == 1:\n",
    "                history_dict[cur_val] = 0\n",
    "                return 0\n",
    "            else:\n",
    "                if cur_val % 2 == 0:\n",
    "                    cur_res = dfs(cur_val // 2) + 1\n",
    "                else:\n",
    "                    cur_res = dfs(cur_val*3+1) + 1\n",
    "                history_dict[cur_val] = cur_res\n",
    "                return cur_res\n",
    "        for val in range(lo, hi+1):\n",
    "            dfs(val)\n",
    "\n",
    "        res = []\n",
    "        for val in range(lo, hi+1):\n",
    "            res.append([history_dict[val], val])\n",
    "        res.sort()\n",
    "\n",
    "        return res[k-1][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKth(self, lo: int, hi: int, k: int) -> int:\n",
    "        # if lo == hi:\n",
    "        #     return lo\n",
    "        # if lo == 1:\n",
    "        #     lo = 2\n",
    "        #     k -= 1\n",
    "        # l = list(range(lo,hi+1))\n",
    "        # count = 0\n",
    "        # while True:\n",
    "        #     for i in range(len(l)):\n",
    "        #         if l[i] == 1:\n",
    "        #             continue\n",
    "        #         if l[i] % 2 == 0:\n",
    "        #             l[i] = l[i] >> 1\n",
    "        #         else:\n",
    "        #             l[i] = 3 * l[i] + 1\n",
    "        #         if l[i] == 1:\n",
    "        #             count += 1\n",
    "        #             if count == k:\n",
    "        #                 return i+lo\n",
    "        \n",
    "        # f = {1: 0}\n",
    "        # def getF(x):\n",
    "        #     if x in f:\n",
    "        #         return f[x]\n",
    "        #     f[x] = (getF(x * 3 + 1) if x % 2 == 1 else getF(x // 2)) + 1\n",
    "        #     return f[x]\n",
    "        \n",
    "        # v = list(range(lo, hi + 1))\n",
    "        # v.sort(key=lambda x: (getF(x), x))\n",
    "        # return v[k - 1]\n",
    "\n",
    "\n",
    "        dp = {1:0}\n",
    "        def f(n):\n",
    "            if n in dp:\n",
    "                return dp[n]\n",
    "            if n % 2 == 0: \n",
    "                dp[n] = f(n >> 1) + 1\n",
    "            else:\n",
    "                dp[n] = f(3*n+1) + 1\n",
    "            return dp[n] \n",
    "        l = list(range(lo,hi+1))\n",
    "        l.sort(key=f)\n",
    "        return l[k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKth(self, lo: int, hi: int, k: int) -> int:\n",
    "        store = {1:1}\n",
    "        def get_depth(x):\n",
    "            if x in store:\n",
    "                return store[x]\n",
    "            if x % 2 == 0:\n",
    "                store[x] = get_depth(x//2) + 1\n",
    "            else:\n",
    "                store[x] = get_depth(3*x+1) + 1\n",
    "            return store[x]\n",
    "        ans = dict()\n",
    "        for i in range(lo, hi+1):\n",
    "            ans[i] = get_depth(i)\n",
    "        res = sorted(ans.items(), key = lambda x:x[1])\n",
    "        return res[k-1][0]\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKth(self, lo: int, hi: int, k: int) -> int:\n",
    "        weight = {1: 0}\n",
    "        def get_weight(x):\n",
    "            if x in weight:\n",
    "                return weight[x]\n",
    "            weight[x] = (get_weight(x * 3 + 1) if x % 2 == 1 else get_weight(x // 2)) + 1\n",
    "            return weight[x]\n",
    "        nums = list(range(lo, hi + 1))\n",
    "        nums.sort(key=lambda x: (get_weight(x), x))\n",
    "        return nums[k - 1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKth(self, lo: int, hi: int, k: int) -> int:\n",
    "        self.memo = {}\n",
    "        self.memo[1] = 0\n",
    "\n",
    "        def get_wight(n):\n",
    "            if n in self.memo:\n",
    "                return self.memo[n]\n",
    "            \n",
    "            if n % 2 == 0:\n",
    "                self.memo[n] = get_wight(n // 2) + 1\n",
    "            else:\n",
    "                self.memo[n] = get_wight(3 * n + 1) + 1\n",
    "            return self.memo[n]\n",
    "        \n",
    "\n",
    "        arr = [n for n in range(lo, hi+1)]\n",
    "        arr.sort(key = lambda x: (get_wight(x), x))\n",
    "        return arr[k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKth(self, lo: int, hi: int, k: int) -> int:\n",
    "        record = {2:1}\n",
    "        def dg(index: int) -> int:\n",
    "            if index in record:\n",
    "                return record[index]\n",
    "            else:\n",
    "                next_index = int(index / 2) if index % 2 == 0 else 3 * index + 1\n",
    "                value = dg(next_index) + 1\n",
    "                record[index] = value\n",
    "                return value\n",
    "        tmp_res = []\n",
    "        for i in range(lo, hi + 1):\n",
    "            value = dg(i)\n",
    "            tmp_res.append((value, i))\n",
    "        tmp_res.sort()\n",
    "        return tmp_res[k-1][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKth(self, lo: int, hi: int, k: int) -> int:\n",
    "        dp={1:1}\n",
    "        def getPower(num):\n",
    "            if num not in dp:\n",
    "                if num%2:\n",
    "                    dp[num]=getPower(3*num+1)+1\n",
    "                else:\n",
    "                    dp[num]=getPower(num//2)+1\n",
    "            return dp[num] \n",
    "        return sorted(list(range(lo,hi+1)),key=getPower)[k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKth(self, lo: int, hi: int, k: int) -> int:\n",
    "        temp=[i for i in range(lo,hi+1)]\n",
    "        dic={1:0}\n",
    "        def f(x):\n",
    "            if x in dic:\n",
    "                return dic[x]\n",
    "            else:\n",
    "                dic[x]=(f(x//2) if x%2==0 else f(x*3+1))+1\n",
    "            return dic[x]\n",
    "        temp.sort(key=f)\n",
    "        return temp[k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKth(self, lo: int, hi: int, k: int) -> int:\n",
    "        number2times = dict()\n",
    "        def f(num):\n",
    "            if num==1: return 0\n",
    "            if num%2==0: target = num//2\n",
    "            else: target = num*3+1\n",
    "            if target in number2times:\n",
    "                times = 1 + number2times[target]\n",
    "            else:\n",
    "                times = 1 + f(target)\n",
    "            number2times[num] = times\n",
    "            return times\n",
    "        arr = []\n",
    "        for num in range(lo, hi+1):\n",
    "            arr.append((f(num), num))\n",
    "        return list(sorted(arr))[k-1][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKth(self, lo: int, hi: int, k: int) -> int:\n",
    "        \n",
    "        weight = dict()\n",
    "        weight[1] = 0\n",
    "\n",
    "        def rec(x):\n",
    "            if x in weight:\n",
    "                return weight[x]\n",
    "            \n",
    "            weight[x] = 1+rec(3*x+1) if x&1 else 1+rec(x//2)\n",
    "            return weight[x]\n",
    "\n",
    "        hashmap = dict()\n",
    "        for i in range(lo, hi+1):\n",
    "            hashmap[i] = rec(i)\n",
    "\n",
    "        res = list(range(lo, hi+1))  \n",
    "        res.sort(key=lambda x:(hashmap[x], x))\n",
    "\n",
    "        return res[k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 30->15->46->23->70->35->106->53->160->80->40->20->10->5->16\n",
    "class Solution:\n",
    "    def getKth(self, lo: int, hi: int, k: int) -> int:\n",
    "        d=defaultdict(list)\n",
    "        s=[]\n",
    "        f={}\n",
    "        def dfs(x):\n",
    "            if x==1:\n",
    "                return 0\n",
    "            elif x==2:\n",
    "                return 1\n",
    "            elif x==4:\n",
    "                return 2\n",
    "            elif x==8:\n",
    "                return 3\n",
    "            elif x==16:\n",
    "                return 4\n",
    "            elif x not in f:\n",
    "                if x%2==0:\n",
    "                    f[x]=dfs(x//2)+1\n",
    "                else:\n",
    "                    f[x]=dfs(3*x+1)+1\n",
    "            return f[x]\n",
    "        for i in range(lo,hi+1):\n",
    "            weight=dfs(i)\n",
    "            d[weight].append(i)\n",
    "            s.append(weight)\n",
    "        s.sort()\n",
    "        w=s[k-1]\n",
    "        index=bisect.bisect_left(s,w)\n",
    "        c=k-1-index\n",
    "        return d[w][c]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getKth(self, lo: int, hi: int, k: int) -> int:\n",
    "        wight_dict = {1: 0}\n",
    "        wight_num_list = []\n",
    "\n",
    "        def wight(x):\n",
    "            if x in wight_dict:\n",
    "                return wight_dict[x]\n",
    "            if x % 2 == 0:\n",
    "                w = 1 + wight(x // 2)\n",
    "            else:\n",
    "                w = 1 + wight(x * 3 + 1)\n",
    "            wight_dict[x] = w\n",
    "            return w\n",
    "\n",
    "        for num in range(lo,hi+1):\n",
    "            wight_num_list.append([num,wight(num)])\n",
    "\n",
    "        wight_num_list.sort(key=lambda item: item[1])\n",
    "        return wight_num_list[k-1][0]\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKth(self, lo: int, hi: int, k: int) -> int:\n",
    "        f = defaultdict(int)\n",
    "        m = list(range(lo, hi+1))\n",
    "        def get(k) -> int:\n",
    "            if k == 1: return 0\n",
    "            if f[k] > 0: return f[k]\n",
    "            if k & 1:\n",
    "                f[k] = get(k * 3 +1) + 1\n",
    "                return f[k]\n",
    "            f[k] = get(k // 2) + 1\n",
    "            return f[k]\n",
    "        m.sort(key=lambda x:(get(x), x))\n",
    "\n",
    "        return m[k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 30->15->46->23->70->35->106->53->160->80->40->20->10->5->16\n",
    "# 记忆化搜索+递归\n",
    "class Solution:\n",
    "    def getKth(self, lo: int, hi: int, k: int) -> int:\n",
    "        d=defaultdict(list)\n",
    "        s=[]\n",
    "        f={}\n",
    "        def dfs(x):\n",
    "            if x==1:\n",
    "                return 0\n",
    "            elif x not in f:\n",
    "                if x%2==0:\n",
    "                    f[x]=dfs(x//2)+1\n",
    "                else:\n",
    "                    f[x]=dfs(3*x+1)+1\n",
    "            return f[x]\n",
    "        for i in range(lo,hi+1):\n",
    "            weight=dfs(i)\n",
    "            d[weight].append(i)\n",
    "            s.append(weight)\n",
    "        s.sort()\n",
    "        w=s[k-1]\n",
    "        index=bisect.bisect_left(s,w)\n",
    "        c=k-1-index\n",
    "        return d[w][c]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKth(self, lo: int, hi: int, k: int) -> int:\n",
    "        f = {1: 0}\n",
    "\n",
    "        def getF(x):\n",
    "            if x in f:\n",
    "                return f[x]\n",
    "            f[x] = (getF(x * 3 + 1) if x % 2 == 1 else getF(x // 2)) + 1\n",
    "            return f[x]\n",
    "        \n",
    "        v = list(range(lo, hi + 1))\n",
    "        v.sort(key=lambda x: (getF(x), x))\n",
    "        return v[k - 1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKth(self, lo: int, hi: int, k: int) -> int:\n",
    "        f = {1: 0}\n",
    "\n",
    "        def getF(x):\n",
    "            if x in f:\n",
    "                return f[x]\n",
    "            f[x] = (getF(x * 3 + 1) if x % 2 == 1 else getF(x // 2)) + 1\n",
    "            return f[x]\n",
    "        \n",
    "        v = list(range(lo, hi + 1))\n",
    "        v.sort(key=lambda x: (getF(x), x))\n",
    "        return v[k - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKth(self, lo: int, hi: int, k: int) -> int:\n",
    "        f = {1: 0}\n",
    "\n",
    "        def getF(x):\n",
    "            if x in f:\n",
    "                return f[x]\n",
    "            f[x] = (getF(x * 3 + 1) if x % 2 == 1 else getF(x // 2)) + 1\n",
    "            return f[x]\n",
    "        \n",
    "        v = list(range(lo, hi + 1))\n",
    "        v.sort(key=lambda x: (getF(x), x))\n",
    "        return v[k - 1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def getKth(self, lo: int, hi: int, k: int) -> int:\r\n",
    "\r\n",
    "        cache = {1:0}\r\n",
    "        def dfs(x):\r\n",
    "            x=int(x)\r\n",
    "            if x in cache:\r\n",
    "                return cache[x]\r\n",
    "            if x % 2 ==0:\r\n",
    "                cache[x] = dfs(x/2)+1\r\n",
    "            else:\r\n",
    "                cache[x] = dfs(x*3+1)+1\r\n",
    "            return cache[x]\r\n",
    "            \r\n",
    "        key = list(range(lo,hi+1))\r\n",
    "        # 按值进行排序，如果值相等，按x进行排序\r\n",
    "        key.sort(key=lambda x: (dfs(x), x))\r\n",
    "        \r\n",
    "        return key[k-1]\r\n",
    "\r\n",
    "        \r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKth(self, lo: int, hi: int, k: int) -> int:\n",
    "        memo = {}\n",
    "        weights = []\n",
    "        nums = [i for i in range(lo, hi + 1)]\n",
    "\n",
    "        def dfs(n):\n",
    "            ans = 0\n",
    "            if n == 1:\n",
    "                return 0\n",
    "            if n in memo:\n",
    "                return memo[n]\n",
    "            if n % 2 == 0:\n",
    "                ans += dfs(n//2) + 1\n",
    "            else:\n",
    "                ans += dfs(3 * n + 1) + 1\n",
    "            memo[n] = ans\n",
    "            return memo[n]\n",
    "        # 枚举每个数字进行搜索\n",
    "        for i in nums:\n",
    "            weights.append(dfs(i))\n",
    "        # 冒泡排序\n",
    "        length = len(nums)\n",
    "        for i in range(length-1):\n",
    "            for j in range(length-i-1):\n",
    "                # 先单独比较权重\n",
    "                if weights[j] > weights[j+1]:\n",
    "                    weights[j], weights[j+1] = weights[j+1], weights[j]\n",
    "                    nums[j], nums[j+1] = nums[j+1], nums[j]\n",
    "                # 权重相同，但数值不同\n",
    "                elif weights[j] == weights[j+1] and nums[j] > nums[j+1]:\n",
    "                    weights[j], weights[j+1] = weights[j+1], weights[j]\n",
    "                    nums[j], nums[j+1] = nums[j+1], nums[j]                    \n",
    "        \n",
    "        return nums[k-1]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
